package main

import "fmt"

// 递推公式的斐波那契数列加cache优化
func fib(n int, m map[int]int) int {
	if n < 0 {
		panic("n is negative")
	} else if n == 0 {
		return 0
	} else if n < 3 {
		return 1
	}
	if i, ok := m[n]; ok {
		return i
	}
	m[n] = fib(n-1, m) + fib(n-2, m)
	return m[n]
}

func main() {
	for i := 1; fib(i, map[int]int{}) < 100; i++ {
		fmt.Print(fib(i, map[int]int{}), " ")
	}
}
